;; e1.19

#|
# logarithmic fibonacci

## introduction

picture fibonacci as a successive transformation in the form of:

T(a, b) = (a <- a + b, b <- a) = (a + b, a)

where T(a, b) depicts an iterative step, fib(n) is therefore the nth power of the transformation T, or in short T^n, starting with (a, b) set to the pair (1, 0)

consider T to be the special case of T.pq, where p = 0 and q = 1, with the transformation in the form of:

T.pq(a, b) = T.pq(bq + aq + ap, bp + aq)

NOTE: the dot represents subscript

(out of curiosity, proving equality to specific case T)

T.p=0,q=1(a, b) = T.0,1(b + a + a*0, 0*b + a) = T.0,1(b + a, a)
                = T(a, b) = T(a + b, a)

indeed this weird dissected form T.pq is just an extension of T

## task

now show there exists a transformation T.p',q'(a, b) that is the same as applying T.pq(a, b) twice

T.p',q'(a, b) = T.pq(T.pq(a, b))

now we quite literally apply T.pq twice and see if we can reduce it to simpler form
remember:
- a <- bq + aq + ap
- b <- bp + aq

T.p',q'(a, b) = T.pq(T.pq(a, b))

a <- (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
b <- (bp + aq)p + (bq + aq + ap)q

now expand

a <- (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
a <- bpq + aq^2 + bq^2 + aq^2 + apq + bqp + aqp + ap^2
a <- 2bpq + 2apq + 2aq^2 + bq^2 + ap^2

b <- (bp + aq)p + (bq + aq + ap)q
b <- bp^2 + aqp + bq^2 + aq^2 + apq
b <- 2apq + bp^2 + bq^2 + aq^2

now try to reduce, in a way to make the transformations of a and b resemble the initial shape of:

T.pq(bq + aq + ap, bp + aq)

by reducing as follows (easier to do with b's transformation):

b <- 2apq + bp^2 + bq^2 + aq^2
b <- bp^2 + bq^2 + aq^2 + 2apq
b <- b(p^2 + q^2) + a(q^2 + 2pq)

for T.pq b is transformed as b <- bp + aq
for T.p',q' b is transformed as b <- bp' + aq'
after our reduction, we can half-confidently say that:

p' = p^2 + q^2
q' = 2pq + q^2

but we need to do this for a also:

a <- 2bpq + 2apq + 2aq^2 + bq^2 + ap^2
a <- 2bpq + bq^2 + 2apq + 2aq^2 + ap^2
a <- b(2pq + q^2) + a(2pq + 2q^2 + p^2)

by now, we notice that our a's initial transformation looked like a <- bq + aq + ap, so fit our result to resemble our initial transformation:

a <- b(2pq + q^2) + a(2pq + 2q^2 + p^2)
a <- b(2pq + q^2) + a(2pq + q^2) + a(q^2 + p^2)

for T.pq b is transformed as a <- bq + aq + ap
for T.p',q' a is transformed as a <- bq' + aq' + ap'

we now have confidence of our result for p' and q'

## usage

if it wasn't obvious from the title, this extension T.p',q'(a, b) allows us to calculate fibonacci numbers in theta(log(n)) time, crazy indeed

## disclaimer

blame sicp for making me use this much notation
|#

(define (fib n)
    (fib-iter 1 0 0 1 n ))
(define (fib-iter a b p q count)
    (define (square n) (* n n))
    (define (deltap p q) 
        (+ (square q)
           (square p)))
    (define (deltaq p q) 
        (+ (square q)
           (* 2 q p)))
    (cond ((= count 0) b)
          ((even? count)
            (fib-iter a
                      b
                      (deltap p q)
                      (deltaq p q)
                      (/ count 2)))
          (else
            (fib-iter (+ (* b q) (* a q) (* a p))
                      (+ (* b p) (* a q))
                      p
                      q
                      (- count 1)))))

(fib 0)
(fib 1)
(fib 2)
(fib 3)
(fib 4)
(fib 5)
(fib 6)
(fib 7)
